import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    int m, n;


    public int nearestExit(char[][] maze, int[] entrance) {
        //找到所有出口，看哪些能走通，再找最短路
        m = maze.length;
        n = maze[0].length;

        int ret = 0;

        boolean[][] temp = new boolean[m][n];
        temp[entrance[0]][entrance[1]] = true;

        Queue<int[]> q = new LinkedList<>();

        q.offer(entrance);

        while (!q.isEmpty()) {
            int size = q.size();
            boolean flag = false;
            while (size > 0) {
                size--;
                int[] arr = q.poll();
                int x = arr[0];
                int y = arr[1];
                temp[x][y] = true;
                for (int i = 0; i < 4; i++) {
                    int xx = x + dx[i];
                    int yy = y + dy[i];
                    if (xx >= 0 && yy >= 0 && xx < m && yy < n && !temp[xx][yy] && maze[xx][yy] == '.') {
                        if (xx == 0 || yy == 0 || xx == m - 1 || yy == n - 1) {
                            return ++ret;
                        } else {
                            q.offer(new int[]{xx, yy});
                            temp[xx][yy] = true;
                            flag = true;//处理结尾情况
                        }

                    }
                }
            }
            if (!q.isEmpty()) {
                ret++;
            }
            if (!flag) {
                return -1;
            }
        }

        return ret == 0 ? -1 : ret;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int ret = solution.nearestExit(new char[][]{{'+', '.', '+', '+', '+', '+', '+'},
                {'+', '.', '+', '.', '.', '.', '+'},
                {'+', '.', '+', '.', '+', '.', '+'},
                {'+', '.', '.', '.', '+', '.', '+'},
                {'+', '+', '+', '+', '+', '+', '.'}}, new int[]{0, 1});

        System.out.println(ret);
    }
}
